package recursion;

public class Queen8 {
    private int num = 8;//代表8个皇后
    private int[] array = new int[num];//用一维数组代表棋盘,下标代表第几个皇后,在第几行,值代表在第几列
    private static int count;
    public static void main(String[] args) {
        Queen8 queen8 = new Queen8();
        queen8.put(0);
        System.out.printf("总共有%d种摆法",count);

    }


    //递归摆放皇后
    public void put(int n) {
        if(n==num) {//代表8个皇后摆放完毕,得到一种解法
            println();
            return;
        }
        for (int i = 0; i < num; i++) {
            array[n] = i;//皇后都从第一列开始放
            if(check(n)) {//判断当前这个皇后是否和前面的皇后冲突
                put(n+1);//不冲突,就摆放下一个皇后
            }
            //如果冲突,i++后,当前皇后移动到下一列
            //如果循环结束,都有冲突,不能进入if语句摆放下一个皇后,说明前面皇后摆放有问题
            //循环结束,方法就结束,回退到上一个put方法,继续走for循环,调整上一个皇后的列,就这样进行回溯递归
        }
    }

    //检查第n个皇后和前面0到n-1个皇后的位置是否冲突
    public boolean check(int n) {
        for (int i = 0; i < n; i++) {
            //如果是同一列或是在对角线,则表示冲突,因为每一行只摆放一个皇后,所以不用判断是否在同一行
            if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])) {
                return false;
            }
        }
        return true;
    }

    //打印数组中结果的方法
    public void println() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}
